package com.yanceysong.codetop.s51_s60;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class S60_Mid_78_子集 {
    /**
     * .S60_Mid_78_子集
     * .<p>
     * .LeetCode 链接：<a href="https://leetcode.cn/problems/subsets/">...</a>
     * .<p>
     * .=============================== 题目描述 ===============================
     * .给定一个 互不相同 的整数数组 nums，返回该数组所有可能的子集（即幂集）。
     * .结果集中 不得 包含重复子集，返回顺序可以任意。
     * .<p>
     * .=============================== 示例 ===============================
     * .示例1：nums = [1,2,3]
     * .输出：[
     * . [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
     * .] （顺序可不同）
     * .<p>
     * .示例2：nums = [0]
     * .输出：[[],[0]]
     * .<p>
     * .示例3：nums = []
     * .输出：[] 只有一个空子集 → [[]]
     * .<p>
     * .=============================== 核心标签 ===============================
     * .回溯 / 深度优先搜索 / 位运算 / 枚举 / 子集生成 / 组合搜索
     * .<p>
     * .=============================== 关键洞察 ===============================
     * .对长度为 n 的数组：每个元素都有 “选” 或 “不选” 两种状态 → 2^n 个不同子集。
     * .回溯法本质上是一颗二叉决策树：在第 i 层决定 nums[i] 是否加入当前子集。
     * .位运算法：用二进制位 0/1 表示是否选择对应元素。
     * .<p>
     * .=============================== 回溯决策树 ASCII（示例 nums=[1,2,3]） ===============================
     * .深度 index 表示当前考虑到的元素下标，currentSubset 表示路径（已选择元素）：
     * <p>
     * .                          (start) current=[] index=0
     * .                         /                        \
     * .                  选择1                           不选1
     * .       current=[1] index=1                      current=[] index=1
     * .          /             \                        /             \
     * .      选2               不选2                 选2              不选2
     * .current=[1,2] i=2   current=[1] i=2      current=[2] i=2      current=[] i=2
     * .     /     \           /     \              /     \             /     \
     * .  选3     不选3      选3    不选3         选3    不选3         选3     不选3
     * .[1,2,3] [1,2]     [1,3]   [1]        [2,3]   [2]         [3]     []   ← 叶子：收集
     * <p>
     * .=============================== 两种主要解法 ===============================
     * .1. 回溯/DFS：逐层深入，每到叶子（index==n）收集当前子集。时间 O(n*2^n)。
     * .2. 位运算枚举：从 0 到 (1<<n)-1，每个数字的二进制用于选择元素。时间 O(n*2^n)。
     * .   回溯更直观、易扩展（例如与组合/剪枝结合）；位运算在需要按固定顺序枚举时更紧凑。
     * .<p>
     * .=============================== 复杂度分析 ===============================
     * .设数组长度为 n：
     * .- 子集数量：2^n
     * .- 总输出元素个数之和：n * .2^{n-1} （每个元素在一半子集中出现）
     * .- 时间复杂度：O(n * .2^n)（生成与复制）
     * .- 空间复杂度：O(n) 递归栈（忽略结果存储），结果本身需要 O(n*2^n) 空间。
     * .<p>
     * .=============================== 边界情况 ===============================
     * .1. 空数组：返回 [[]]
     * .2. 单元素：返回 [[],[x]]
     * .3. 已声明互不相同，无需去重逻辑；若有重复需排序 + 跳过重复（本题不需要）。
     * .<p>
     * .=============================== 验证技巧 ===============================
     * .- 检查结果大小是否为 2^n
     * .- 可将每个子集排序后放入 Set，确认无重复
     * .- 专门测试空数组、单元素、典型多元素
     * .<p>
     * .=============================== 总结 ===============================
     * .子集问题是回溯基础题：二叉选择（选/不选），叶子收集；构造思路清晰、易迁移到组合/排列/子序列等场景。
     */

    // 当前路径（已经选择的元素组成的子集）
    private final List<Integer> currentSubset = new ArrayList<>();
    // 所有子集的集合
    private final List<List<Integer>> allSubsets = new ArrayList<>();

    /**
     * .回溯主入口：生成所有子集。
     * .@param nums 互不相同的整数数组
     * .@return 所有子集列表
     */
    public List<List<Integer>> subsets(int[] nums) {
        allSubsets.clear();
        currentSubset.clear();
        backtrack(0, nums); // 从下标 0 开始决策
        return allSubsets;
    }

    /**
     * .回溯（深度优先搜索）函数：在位置 index 决定是否选 nums[index]。
     * .@param index 当前考虑的数组下标
     * .@param nums 输入数组
     */
    private void backtrack(int index, int[] nums) {
        // 终止：所有元素都已决定 → 收集当前路径副本作为一个子集
        if (index == nums.length) {
            allSubsets.add(new ArrayList<>(currentSubset));
            return;
        }
        // 选择当前元素
        currentSubset.add(nums[index]);
        // 递归进入下一层决策
        backtrack(index + 1, nums);
        // 回溯撤销选择
        currentSubset.remove(currentSubset.size() - 1);

        // 不选择当前元素
        backtrack(index + 1, nums);
    }

    /**
     * .位运算法：通过 0..(1<<n)-1 遍历所有选择状态。
     * .@param nums 输入数组
     * .@return 所有子集
     */
    public List<List<Integer>> subsetsBitMask(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>(1 << n);
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int bit = 0; bit < n; bit++) {
                if ((mask & (1 << bit)) != 0) { // 该位为1表示选择
                    subset.add(nums[bit]);
                }
            }
            result.add(subset);
        }
        return result;
    }

    // ======================== 测试与辅助方法 ========================

    /**
     * .打印一个子集列表
     */
    private static void printSubsets(List<List<Integer>> subsets) {
        System.out.print("[");
        for (int i = 0; i < subsets.size(); i++) {
            System.out.print(subsets.get(i));
            if (i < subsets.size() - 1) System.out.print(", ");
        }
        System.out.println("] (总数=" + subsets.size() + ")");
    }

    /**
     * .将子集列表转为 Set<String> (用于快速比较忽略顺序)
     */
    private static Set<String> toSignatureSet(List<List<Integer>> subsets) {
        Set<String> set = new HashSet<>();
        for (List<Integer> s : subsets) {
            List<Integer> copy = new ArrayList<>(s);
            Collections.sort(copy); // 规范化排序
            set.add(copy.toString());
        }
        return set;
    }

    /**
     * .验证结果规模是否正确且与位运算法一致
     */
    private static void verify(int[] nums, List<List<Integer>> backtrackRes, List<List<Integer>> bitmaskRes) {
        int n = nums.length;
        int expectedSize = 1 << n;
        assert backtrackRes.size() == expectedSize : "回溯法结果规模错误";
        assert bitmaskRes.size() == expectedSize : "位运算法结果规模错误";
        Set<String> a = toSignatureSet(backtrackRes);
        Set<String> b = toSignatureSet(bitmaskRes);
        assert a.equals(b) : "两种实现的子集集合不一致";
    }

    public static void main(String[] args) {
        System.out.println("=== 子集生成测试开始 ===\n");
        S60_Mid_78_子集 solver = new S60_Mid_78_子集();

        // 测试1：空数组
        int[] nums1 = {};
        System.out.println("测试1：空数组 []");
        List<List<Integer>> r1 = solver.subsets(nums1);
        List<List<Integer>> r1b = solver.subsetsBitMask(nums1);
        printSubsets(r1);
        verify(nums1, r1, r1b);
        System.out.println("✓ 空数组测试通过\n");

        // 测试2：单元素
        int[] nums2 = {5};
        System.out.println("测试2：单元素 [5]");
        List<List<Integer>> r2 = solver.subsets(nums2);
        List<List<Integer>> r2b = solver.subsetsBitMask(nums2);
        printSubsets(r2);
        verify(nums2, r2, r2b);
        System.out.println("✓ 单元素测试通过\n");

        // 测试3：两个元素
        int[] nums3 = {1, 2};
        System.out.println("测试3：两个元素 [1,2]");
        List<List<Integer>> r3 = solver.subsets(nums3);
        List<List<Integer>> r3b = solver.subsetsBitMask(nums3);
        printSubsets(r3);
        verify(nums3, r3, r3b);
        System.out.println("✓ 两元素测试通过\n");

        // 测试4：三个元素
        int[] nums4 = {1, 2, 3};
        System.out.println("测试4：三个元素 [1,2,3]");
        List<List<Integer>> r4 = solver.subsets(nums4);
        List<List<Integer>> r4b = solver.subsetsBitMask(nums4);
        printSubsets(r4);
        verify(nums4, r4, r4b);
        System.out.println("✓ 三元素测试通过\n");

        // 测试5：四个元素（结果 16 个）
        int[] nums5 = {4, 5, 6, 7};
        System.out.println("测试5：四元素 [4,5,6,7]");
        List<List<Integer>> r5 = solver.subsets(nums5);
        List<List<Integer>> r5b = solver.subsetsBitMask(nums5);
        printSubsets(r5);
        verify(nums5, r5, r5b);
        System.out.println("✓ 四元素测试通过\n");

        // 测试6：包含 0 与正负数
        int[] nums6 = {-1, 0, 2};
        System.out.println("测试6：含负数与0 [-1,0,2]");
        List<List<Integer>> r6 = solver.subsets(nums6);
        List<List<Integer>> r6b = solver.subsetsBitMask(nums6);
        printSubsets(r6);
        verify(nums6, r6, r6b);
        System.out.println("✓ 负数与0测试通过\n");

        // 测试7：顺序不影响结果（验证与排序无关性）
        int[] nums7a = {1, 3, 2};
        int[] nums7b = {1, 2, 3};
        System.out.println("测试7：不同输入顺序 [1,3,2] vs [1,2,3]");
        List<List<Integer>> r7a = solver.subsets(nums7a);
        List<List<Integer>> r7b = solver.subsets(nums7b);
        Set<String> sigA = toSignatureSet(r7a);
        Set<String> sigB = toSignatureSet(r7b);
        assert sigA.equals(sigB) : "不同顺序的输入应产生相同子集集合";
        System.out.println("✓ 顺序无关性测试通过\n");

        System.out.println("=== 所有子集测试完成 ===");
    }
}
